/**
 * @author 雷明浩
 * @date 2025/6/3 14:59
 */
public class IsPail {
    // newcoder 判断一个链表是否为回文结构
    // https://www.nowcoder.com/practice/3fed228444e740c8be66232ce8b87c2f?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page
    public boolean isPail (ListNode head) {
        // write code here
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            if (fast == null) {
                break;
            }
            slow = slow.next;
        }
        ListNode slowNext = slow.next;
        slow.next = null;
        ListNode nextList = reverseList(slowNext);
        ListNode cur1 = head;
        ListNode cur2 = nextList;
        while (cur1 != null && cur2 != null) {
            if (cur1.val != cur2.val) {
                return false;
            }
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return true;
    }

    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return prev;
    }
}